package main

func main() {
	// [226. 翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/)
	// [101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/)
	// [104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)
	// [111. 二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)
	// [222. 完全二叉树的节点个数](https://leetcode.cn/problems/count-complete-tree-nodes/)
}

// 226
func invertTree(root *TreeNode) *TreeNode {
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		node.Left, node.Right = node.Right, node.Left
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)
	return root
}

// 101
func isSymmetric(root *TreeNode) bool {
	queue := make([]*TreeNode, 0)
	if root != nil {
		queue = append(queue, root.Left)
		queue = append(queue, root.Right)
	}
	for len(queue) > 0 {
		right, left := queue[len(queue)-1], queue[len(queue)-2]
		queue = queue[:len(queue)-2]
		if right == nil && left == nil {
			continue
		}
		if right == nil || left == nil {
			return false
		}
		if right.Val != left.Val {
			return false
		}
		queue = append(queue, right.Right)
		queue = append(queue, left.Left)
		queue = append(queue, right.Left)
		queue = append(queue, left.Right)
	}
	return true
}

// 104
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := maxDepth(root.Left)
	right := maxDepth(root.Right)
	return max(left, right) + 1
}
func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

// 111
func minDepth(root *TreeNode) int {
	//dfs
	if root == nil {
		return 0
	}
	left := minDepth(root.Left)
	right := minDepth(root.Right)
	if root.Left == nil && root.Right != nil {
		return right + 1
	} else if root != nil && root.Right == nil {
		return left + 1
	}
	return min(left, right) + 1
	//bfs
	queue := make([]*TreeNode, 0)
	if root != nil {
		queue = append(queue, root)
	}
	ans := 0
	for len(queue) > 0 {
		ans++
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			if node.Left == nil && node.Right == nil {
				return ans
			}
		}
	}
	return ans
}

// dfs
func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

// 222
func countNodes(root *TreeNode) int {
	queue := make([]*TreeNode, 0)
	ans := 0
	if root != nil {
		queue = append(queue, root)
	}
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
			ans++
		}
	}
	return ans
}
